<?php
/**
 * 难度：简单
 * 题目链接 https://leetcode.cn/problems/search-insert-position/description/
 */

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return int
     */
    public static function searchInsert1(array $nums, $target): int 
    {
        $start = 0;
        $end = count($nums) - 1;

        while ($start <= $end) {
            $mid = intval(($start + $end) / 2);
            // echo "start=$start end=$end mid=$mid" . PHP_EOL;
            if ($target < $nums[$start]) {
                // 在起始前面
                return $start - 1 <= 0 ? 0 : $start - 1;
            } elseif ($target > $nums[$end]) {
                // 在结尾后面
                return $end + 1;
            } else {
                if ($target < $nums[$mid]) {
                    // 值在中间靠左
                    $end = $mid;
                } elseif ($target > $nums[$mid]) {
                    // 值在中间靠右
                    if ($start == $mid) {
                        // 防止死循环
                        return $start + 1;
                    }
                    $start = $mid;
                } else {
                    // 刚好命中中间
                    return $mid;
                }
            }
        }
        
        // 没命中 停止循环
        return $start + 1;
    }

    /**
     * 简化一下写法
     * @param Integer[] $nums
     * @param Integer $target
     * @return int
     */
    public static function searchInsert(array $nums, $target): int 
    {
        $start = 0;
        $end = count($nums);

        while (1) {
            if ($start == $end) {
                return $start;
            }
            $mid = $start + intval(($end - $start) / 2);
            if ($nums[$mid] == $target) {
                return $mid;
            } elseif ($nums[$mid] > $target) {
                $end = $mid;
            } else {
                $start = $mid + 1;
            }
        }
    }
}

$test = [
    [[1,3,5,6], 5],
    [[1,3,5,6], 2],
    [[1,3,5,6], 7],
];
$result = [
    2,
    1,
    4,
];

foreach ($test as $key => $value) {
    $r = Solution::searchInsert($value[0], $value[1]);
    if ($r !== $result[$key]) {
        echo sprintf("第%d个case不通过", $key) . PHP_EOL;
    }
    echo $r . PHP_EOL;
}